package com.leetcode.study;

/**
 * 最长回文子串
 *
 * https://leetcode.cn/problems/longest-palindromic-substring/description/
 *
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 *
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 *
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 *
 */
public class L5 {

    public static void main(String[] args) {

        String s = "lphntrsqudccteewsdmpjmgmfnxegawjclzobpnxdrvxeygafiwyqsvsecictqkmiqvrdjajfngvlhdezdpqpzjjzbhoyggrbkuzeocrpzqishvfairdvvabopyubfisxbrgnlughbrzunitwowvnsqhdtnkotitgxwzjhbgltksorygpdberdgzgvogrvwluhixfbrfhliedjylxuspjpitwlhdkneonreqrueqphirmgxtqumllqropaefddplspkrtkbmuvwkyryworojlvwzdlacuoqzokrmcgmwkopsbqjjkaoqjqbrderwzmhbhfgwvrjakyfeqcbtvlcgbsxkngymxyievihiskdmmppmmdksihiveiyxmygnkxsbgclvtbcqefykajrvwgfhbhmzwredrbqjqoakjjqbspokwmgcmrkozqoucaldzwvljorowyrykwvumbktrkpslpddfeaporqllmuqtxgmrihpqeurqernoenkdhlwtipjpsuxlyjdeilhfrbfxihulwvrgovgzgdrebdpgyrosktlgbhjzwxgtitokntdhqsnvwowtinuzrbhgulngrbxsifbuypobavvdriafvhsiqzprcoezukbrggyohbzjjzpqpdzedhlvgnfjajdrvqimkqtcicesvsqywifagyexvrdxnpbozlcjwagexnfmgmjpmdsweetccduqsrtnhpl";

        //s = "ababac";
        System.out.println(longestPalindrome(s));
        System.out.println(longestPalindrome0(s));
        System.out.println(longestPalindrome1(s));

    }
    /**
     * 动态规划是一种解决问题的数学方法，通常用于优化问题和组合问题。 <br/>
     * 它的基本思想是将原问题分解成更小的子问题，然后根据子问题的解推导出原问题的解，通过存储子问题的解来避免重复计算，从而提高效率。 <br/>
     * 动态规划通常适用于具有重叠子问题和最优子结构性质的问题，这意味着问题的解可以通过子问题的解来求解，并且子问题之间存在重叠。 <br/>
     *
     * 动态规划的核心思想是将问题分解成多个子问题，并且利用已经解决过的子问题的结果来加速解决当前问题。 <br/>
     * 这种方法通常需要设计递推关系和合适的数据结构来存储子问题的解，从而实现高效的问题求解。 <br/>
     * 动态规划常被用于解决各种问题，例如最长公共子序列、背包问题、最短路径等。通过合理的分析和设计，动态规划可以大大提高问题的求解效率。 <br/>
     *
     *
     * 思路与算法
     *
     * 对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。 <br/>
     * 例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。 <br/>
     *
     * 先看子串是不是回文字符串，再看子串的上一层字串，直到看到整个字符串 <br/>
     * 复杂度分析
     *
     * 时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
     *
     * 空间复杂度：O(n^2)，即存储动态规划状态需要的空间。
     * @param s
     * @return
     */
    public static String longestPalindrome1(String s) {
        // 1、对于长度<2的字符串，直接返回。空值和一个字母本身就是回文串
        // 回文串的定义是一个正读和反读都相同的字符串，因此长度为 1 的子串本身就是回文串
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        // 把所有的字符拆开，单个看都是回文串，所以标记了当个字符串都是1
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        int leg = 0;
        char[] charArray = s.toCharArray();

        // P(i,j) 表示字符串 s 的第 i 到 j 个字母组成的串，是否为回文串
        // 2、对于>=2的字符串，
        //         * 分割字串，并判断字串长度为：n+1 ... s.length时，是否为回文串
        //         * 比如：字串长度为：2
        //         *      字串长度为：3
        //         *      字串长度为：4
        //         *      字串长度为：5
        //         *      字串长度为：...
        //         *      字串长度为：s.length
        // 递推开始
        // 先枚举子串长度 L代表回文串的长度： j−i+1（即子串长度）的最大值，所以他是可以等于数组长度的
        // 回文串的定义是一个正读和反读都相同的字符串，因此长度为 1 的子串本身就是回文串，需要考虑长度至少为2的子串。
        for (int L = 2; L <= len; L++) {
            leg = L;
            System.out.println("子串长度为：" + leg);

            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;

                // 如果右边界越界，就可以退出当前循环，数组的右边界不能等于数组长度，会越界
                if (j >= len) {
                    break;
                }

                // 如果两端的字母不相等，那一定不是回文字符串
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;

                } else {
                    // 如果两端相等并且子串长度小于3(即只有1个或2个字符)，那么该子串一定是回文串
                    if (j - i < 3) {
                        dp[i][j] = true;

                    } else {
                        // 如果两端相等且子串长度大于等于3，则取决于去掉两端字符的子串是否为回文串
                        // 对于去掉两端字符的子串我们已经比较完了，比如子串长度为5，去掉两端则子串长度为3，是我们已经比较完的过程，并且结果记录在dp[i][j]中了
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串s[i..j] 是回文并且如果当前子串是回文串且长度大于记录的最长回文子串长度，
                // 此时记录回文长度和起始位置
                //if (dp[i][j] && j - i + 1 > maxLen) {
                if (dp[i][j] && L > maxLen) {

                    // 更新最长回文子串的长度
                    //maxLen = j - i + 1;
                    maxLen = L;
                    // 更新起始位置，将此次最长回文串查找的起始位置赋值给begin
                    begin = i;
                }
            }
        }

        System.out.println("回文串最大长度：" + maxLen);

        return s.substring(begin, begin + maxLen);
    }


    /**
     * 借鉴网友的，用于验证
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        int length = s.length();
        String maxStr="";
        String reverse=new StringBuffer(s).reverse().toString();

        int x=0;
        int y=1;
        while (x<length&&y<=length){
            String substring = s.substring(x, y);
            if (reverse.contains(substring)){
                if(substring.equals(new StringBuffer(substring).reverse().toString())) {
                    if (substring.length()>maxStr.length()){
                        maxStr=substring;
                    }
                }
                y++;
            }else {
                x++;
                y=x+1;
            }
        }

        return maxStr;
    }

    /**
     * 这和暴力解法相似，当使用while循环时时间复杂度为0(n)，当使用双重for循环时间复杂度为0(n^2)，力扣直接超时了
     * @param s
     * @return
     */
    public static String longestPalindrome0(String s) {
        // 将字符串反转
        /*String reverseStr = "";
        for (int i = s.length() - 1; i > -1; i--) {
            reverseStr = reverseStr + s.charAt(i);
        }*/

        String reverseStr = new StringBuffer(s).reverse().toString(); //字符串倒置


        String resStr = "";
        int i = 0, j = 0;

        while (i < reverseStr.length() && j < reverseStr.length()) {
            String substring = s.substring(i, j+1);
            if (reverseStr.contains(substring)) {

                if (substring.equals(new StringBuffer(substring).reverse().toString())) {
                    if (substring.length() > resStr.length()) {
                        resStr = substring;
                    }
                }

                j++;

            } else {
                i++;
                j = i;
            }
        }
        /*for (int i = 0; i < reverseStr.length(); i++) {
            for (int j = i; j < reverseStr.length(); j++) {
                String substring = reverseStr.substring(i, j + 1);

                if (s.contains(substring) && substring.equals(new StringBuffer(substring).reverse().toString())) {

                    if (substring.length() > resStr.length()) {
                        resStr = substring;
                    }
                }
            }

        }*/

        return resStr;
    }
}
